import copy  # 实现深拷贝！！！
import xlsxwriter, re
from buffer import Buffer

arm_time = 150
best_time = 99999999  # 先搞一个很大的值

stage_list_full = [
    #[(任务标识)，(操作序号，操作资源，时间，前置任务依赖，(die,page)), (...))
    ["r1",(1,"nfc1",200,(0,),(1,0)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
    ["r2",(1,"nfc2",200,(0,),(2,2)),(2,'arm',1,(1,)),(3,'host',20,(2,))],
    ["r3",(1,"nfc2",200,(0,),(2,3)),(2,'arm',1,(1,)),(3,'host',20,(2,))],
    ["r4",(1,"nfc2",200,(0,),(2,4)),(2,'arm',1,(1,)),(3,'host',20,(2,))],
    ["w1",(1,"nfc1",200,(0,),(1,1)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
    ["w2",(1,"nfc1",200,(0,),(1,3)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
    ["w3",(1,"nfc1",200,(0,),(1,4)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
    ["w4",(1,"nfc2",200,(0,),(2,5)),(2,"arm",1,(1,)),(3,"host",20,(2,))],
    ["t",
        (1,"host",20,(0,)),
        (2,"nfc1",200,(1,),(1,2)),
        (3,"arm",1,(2,)),
        (4,"nfc1",200,(3,),(1,0)),
        (5,"arm",1,(4,)),
        (6,"arm",arm_time,(5,)),
        (7,"nfc2",200,(3,),(2,0)),
        (8,"arm",1,(7,)),
        (9,"arm",arm_time,(8,)),
        (10,"host",20,(6,9,))    
        ]
]

def get_stage_list_lite():  # 做格式转换
    stage_list_lite = []
    for task in stage_list_full:
        stages = []
        for stage in task[1:]:  # 遍历处理
            if len(stage) == 5:  # 带了page元组的，末尾加上page
                stage_str = task[0] + "-" + str(stage[0]) + "-" + stage[1] + "-" + str(stage[2]) + "-" + str(stage[3]) + "-" + str(stage[4])
            elif len(stage) == 4:  # 没有带page元组，末尾不加page
                stage_str = task[0] + "-" + str(stage[0]) + "-" + stage[1] + "-" + str(stage[2]) + "-" + str(stage[3]) + "-"
            stages.append(stage_str)
        stage_list_lite.append(stages)
    return stage_list_lite


# 计算可能的合法顺序，采用递归的思想来实现
def compute_legal_order(stage_list_lite:list):
    # f = open('legal_order_r.txt', 'w')    

    def generate_order(order_str:str, remanent_tasks:list):  # 递归函数
        time = compute_order_time(order_str[:-3])  # 先计算下序列所需要的执行时间
        global best_time
        if time > best_time:  # 如果现在所需的执行时间已经比最佳时间长了
            return  # 那就不用继续往下面算了

        # 判断remanent_tasks是否为空，空的话就结束递归
        remanent_tasks_is_empty = True  # 先假设是空的
        for task in remanent_tasks:
            if len(task) > 0:
                remanent_tasks_is_empty = False
                break
        if remanent_tasks_is_empty:
            # order_str = order_str[:-3] + '\n'
            # f.write(order_str)
            if time < best_time:
                best_time = time  # 更新best_time
                print(best_time)
            return  # 结束递归，向上返回

        remanent_tasks_copy = copy.deepcopy(remanent_tasks)  # 在下面的候选池提取环节中会破坏列表，所有先深拷贝一份，然后在副本上操作
        usable_stages = []  # 先初始化一个空池子
        # 从remanent_tasks_copy中找出所有可用的stage放到候选池中去
        for remanent_task_index in range(len(remanent_tasks_copy)):  # 遍历每一个剩余的task
            # 只管task不为空的情况，空着就空着吧，不要删，否则接下来检查前置的时候没法从任务表中定位任务
            while remanent_tasks_copy[remanent_task_index]:  # 在不为空的task中一直找下去，把能拿的都拿到候选池中
                stage_words = remanent_tasks_copy[remanent_task_index][0].split('-')  # 取第一个stage做个切割，拿其前置依赖
                depend_table = tuple(eval(stage_words[4]))  # 转换得到依赖表
                this_stage_can_be_issue = True  # 先假设此stage的前置依赖都做完了，可以放到候选池中发射
                for depend_stage_num in depend_table:  # 检查依赖
                    # 实际上，如果是任务的第一个stage，那么depend_stage_num - 1后会得到-1，从而指向最后一个stage，但不影响功能
                    if stage_list_lite[remanent_task_index][depend_stage_num - 1] in usable_stages:  # 如果所依赖的stage在候选池里，那么说明其前置未完成，此stage不能发射
                        this_stage_can_be_issue = False
                        break  # 不用再看后面的依赖了
                if this_stage_can_be_issue:  # 如果此stage可以放到候选池里等待发射
                    usable_stages.append(remanent_tasks_copy[remanent_task_index][0])  # 把这个stage放到候选池里
                    remanent_tasks_copy[remanent_task_index] = remanent_tasks_copy[remanent_task_index][1:]  # 利用切片的方法将stage从剩余stages中剔除
                else:  # 此stage不能放到候选池中
                    break  # 那就离开这个task

        for stage in usable_stages:  # 从候选池中依次拿一个stage
            new_order_str = order_str + stage + '>>>'  # 此处不能在原order_str上进行操作，否则下次循环还会保留上次的结果

            remanent_tasks_copy = copy.deepcopy(remanent_tasks)  # 做一个深拷贝，从中移除已经选了的stage，并将剩余的task传给下一层递归
            for task in remanent_tasks_copy:
                if stage in task:
                    task.remove(stage)
                    break
            generate_order(new_order_str, copy.deepcopy(remanent_tasks_copy))  # 进入下一层的递归


    generate_order('', copy.deepcopy(stage_list_lite))  # 开始进行递归
    # f.close()


# 下面几个函数专门用于计算执行时间
def init_resourses():  # 用来构造初始状态的可用资源表
    resource = {
        'nfc1': ['0-0<>'],
        'nfc2': ['0-0<>'],
        'host': ['0-0<>'],
        'm1': ['0-0<>'],
        'm2': ['0-0<>'],
        'arm': ['0-0<>'],
    }

    return resource

def init_done_table():  # 用来存储已经完成的stage信息，方便查找所依赖的stage的完成时间
    done_table = {}
    for task in stage_list_full:
        done_table[task[0] + '-0'] = 0
    return done_table

# todo: 计算时间
def compute_order_time(exe_order_str:str):  # 计算每种执行顺序的时间
    if not exe_order_str:
        global best_time
        return best_time - 1
    # order_file = open('legal_order_r.txt', 'r')
    # all_lines = order_file.readlines()
    # order_file.close()
    # workbook = xlsxwriter.Workbook('exeTime_r.xlsx')  # 将每种顺序的执行情况记录到exeTime.xlsx里面
    # worksheet = workbook.add_worksheet()  # 创建一个新的sheet
    # # 先写第一行的title
    # worksheet.write('A1', 'host')
    # worksheet.write('B1', 'nfc1')
    # worksheet.write('C1', 'nfc2')
    # worksheet.write('D1', 'arm')
    # worksheet.write('E1', 'm1')
    # worksheet.write('F1', 'm2')
    # worksheet.write('G1', 'Time')
    # # 构造一个字典，用于得到不同title在表格中所对应的列名
    # col_prefix = {'host':'A', 'nfc1':'B', 'nfc2':'C', 'arm':'D', 'm1':'E', 'm2':'F', 'Time':'G'}

    # row_index = 1  # 用于确定当前order应该写到excel的哪一行
    # for exe_order_str in all_lines:  # 遍历每一种执行顺序
    #     row_index += 1  # 第0行是标题行，所以要先切到下一行
    #     # sys_time = 0  # 初始的时间戳
    resources = init_resourses()  # 算每一种order都要重新构造一个新的
    done_table = init_done_table()  # 初始化一个字典，用来存每个stage的完成时间
    buffer_list = [Buffer(2), Buffer(2)]  # 分别对应nfc1和nfc2，默认每个buffer深度为1

    stage_list = exe_order_str.split('>>>')
    for stage in stage_list:  # 开始对stage_list中的每一个stage处理，将其放到对应的位置并计算时间
        words = stage.split('-')  # 先做个切割
        unit_name = words[2]  # 此stage所需的器件。之所以要单独存个变量是因为后面如果是matcher的话unit会发生变化
        # 拿前置依赖stage的完成时间和器件的空闲时间，以两者之间较久的那个为准
        # 先查前置依赖的完成时间，便于分配可用器件
        last_depend_done_time = 0
        depend_stages = tuple(eval(words[4]))
        for stage_index in depend_stages:  # 挨个遍历前置依赖
            if done_table[words[0] + '-' + str(stage_index)] > last_depend_done_time:  # 选择完成时间最晚的那一个存下来
                last_depend_done_time = done_table[words[0] + '-' + str(stage_index)]

        # 拿器件空闲时间
        # unit_free_time = 0
        # if words[2] == 'matcher':  # 需要先分配一个确定的matcher
        #     matcher1_free_time = int(re.match(r'\d+-(\d+)<\w*', resources['m1'][-1]).group(1))  # 这是m1的
        #     matcher2_free_time = int(re.match(r'\d+-(\d+)<\w*', resources['m2'][-1]).group(1))  # 这是m2的
        #     if matcher1_free_time <= matcher2_free_time:  # 如果m1的空闲时间<=m2的，那就分配到m1上
        #         unit_name = 'm1'
        #         unit_free_time = matcher1_free_time
        #     else:  # 分配到m2上
        #         unit_name = 'm2'
        #         unit_free_time = matcher2_free_time

        # else:  # 不是匹配操作，查resources字典
        last_op = resources[words[2]][-1]  # 拿对应器件的最后执行操作
        unit_free_time = int(re.match(r'\d+-(\d+)<\w*', last_op).group(1))  # 用正则表达式从'0-0<>'中提取出结束时间

        operation_time = int(words[3])
        # 检查buffer命中情况
        if words[5]:  # 如果是需要buffer的
            buffer_info = tuple(eval(words[5]))  # (dieNo, page)
            buffer_instance = buffer_list[buffer_info[0] - 1]  # 先拿到对应channel的buffer instance
            if buffer_instance.is_hit(buffer_info[1]):  # 如果buffer命中了
                operation_time = 0
            else:  # 未命中，则先分配一个
                if not buffer_instance.allocate(buffer_info[1]):  # allocate返回了False，说明需要先进行写回
                    operation_time += 600  # 增加一段写回的时间
            if words[0].startswith('w'):  # 如果是一个host写操作，则需要将buffer置脏
                buffer_instance.mark_dirty(buffer_info[1])
        
        # 接下来就需要计算stage的起始-终止时间了，并保存结果
        start_time = last_depend_done_time if last_depend_done_time > unit_free_time else unit_free_time  # 确定起始时间
        end_time = start_time + operation_time  # 确定结束的时间
        # 记录结果
        resources[unit_name].append(str(start_time) + '-' + str(end_time) + '<' + words[0] + '-' + words[1] + '>')  # 添加到器件时间表中
        done_table[words[0] + '-' + words[1]] = end_time  # 标记此stage的完成时间，便于下次拿前置stage的完成时间

    # 统计此order的最终执行时间
    total_time = sorted(done_table.items(), key = lambda kv:(kv[1], kv[0]))[-1][1]  # 直接对done_table按值排序即可拿到完成时间最晚的那个stage
    return total_time
        # worksheet.write(col_prefix['Time'] + str(row_index), total_time)  # 把总时间写道表格中去

        # # 将每个器件的执行情况写到表格中去
        # for name in resources:  # 遍历resources的键
        #     if len(resources[name]) > 1:
        #         content = ', '.join(resources[name][1:])  # 先要拼接成一个字串
        #         worksheet.write(col_prefix[name] + str(row_index), content)  # 将content写到excel对应的cell中去

        # break

    
    # workbook.close()

compute_legal_order(get_stage_list_lite())  # 先算所有的合法排列
# compute_order_time()  # 计算执行总时间
print(best_time)
